package com.lry.basic.algorithm.dp;

import java.util.Arrays;

public class PickTask {
    public static void main(String[] args) {
        System.out.println(new PickTask().pickTask(new int[][]{{1, 3}, {2, 4}, {3, 5}}));

        System.out.println(new PickTask().pickTask(new int[][]{{1, 2}, {2, 3}, {3, 4},{1,6}},new int[]{1,3,1,6}));

    }



    //如何挑选最多数量的任务,任务只能串行，开始时间和结束时间，不能交叉
    public int pickTask(int[][] tasks){
        if(tasks.length<=1){
            return 0;
        }

        Arrays.sort(tasks,(int[] a, int[]b)-> a[1]-b[1]);

        int ans = 1;
        int temp = tasks[0][1];


        for(int i=1;i<tasks.length;++i){
            if(tasks[i][0]>=temp){
                temp = tasks[i][1];
                ans++;
            }
        }

        return ans;
    }

    /**
     *
     * @param tasks 任务数组，列为2，开始时间和结束时间，任务不可以交叉，只能串行执行
     * @param value 每个任务所获得的价值
     * @return 求最大价值
     */
    public int pickTask(int[][] tasks,int[] value){
        if(tasks.length<=0){
            return 0;
        }
        return dfs(0,0,tasks,value);
    }

    public int dfs(int i,int maxEnd,int[][]tasks,int[]value){
        if(i==value.length){
            return 0;
        }
        //不能选第i个任务
        else if(tasks[i][0]<maxEnd){
            return dfs(i+1,maxEnd,tasks,value);
        }else{
            //选第i个任务，不选
            return Math.max(dfs(i+1,tasks[i][1]>maxEnd?tasks[i][1]:maxEnd,tasks,value)+value[i],dfs(i+1,maxEnd,tasks,value));
        }
    }
}
